package SubjectArray;

import java.util.Arrays;

public class MinSubArrayLen {

/**
 * 难度：中等
 * 
 * 209. 长度最小的子数组
 * 	给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。
 * 	如果不存在符合条件的子数组，返回 0。
 * 
 * 示例：
 * 	输入：s = 7, nums = [2,3,1,2,4,3]
 * 	输出：2
 * 	解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * 
 * 进阶：
 * 	如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
 *
 * */		

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MinSubArrayLen msa = new MinSubArrayLen();
		System.out.println(msa.minSubArrayLen3(7, new int[] {2,3,1,2,4,3}));
	}
	
	//方法一：暴力法
	public int minSubArrayLen1(int s, int[] nums) {
		int n = nums.length;
		if(n==0)return 0;
		
		int ans = Integer.MAX_VALUE;
		for(int i=0;i<n;i++) {
			int sum=0;
			for(int j=i;j<n;j++) {
				sum+=nums[j];
				if(sum>=s) {
					ans = Math.min(ans, j-i+1);
					break;
				}
			}
		}
		return ans==Integer.MAX_VALUE?0:ans;
    }
	
	//方法二：前缀和 + 二分查找
	public int minSubArrayLen2(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算，令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
            System.out.println(sums[i]);
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
	//方法三：双指针
	public int minSubArrayLen3(int s, int[] nums) {
		int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start=0,end=0;
        int sum=0;
        while(end<n) {
        	//此处循环移动尾部，直至统加的值大于等于s
        	sum+=nums[end];
        	while(sum>=s) {
        		//记录连续子数组个数
        		ans = Math.min(ans, end-start+1); 
        		//把头部的数值移除出来
        		sum-=nums[start];
        		//再循环移动头部
        		start++;
        	}
        	end++;
        }
		return ans == Integer.MAX_VALUE ? 0 : ans;
	}
}
